class Solution {//leetcode1049——最后一块石头重量II
public:
    int lastStoneWeightII(vector<int>& stones) {
        int n=stones.size();
        int sum=0;
        for(auto e:stones){
            sum+=e;
        }
        int aim=sum/2;
        vector<vector<int>> dp(n+1,vector<int>(aim+1));
        for(int i=1;i<n+1;i++){
            for(int j=1;j<aim+1;j++){
                dp[i][j]=dp[i-1][j];
                if(j-stones[i-1]>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
            }
        }
        return sum-dp[n][aim]-dp[n][aim];

    }
};